package leetcode.editor.cn;

/**
 * @author: yangwk
 * @date: 2023/3/21
 * @description:
 **/
public class P106ConstructBinaryTreefromInorderandPostorderTraversal {
    int index = 0;
    int[] inorder = {9, 3, 15, 20, 7}, postorder = {9, 15, 7, 20, 3};

    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7}, postorder = {9, 15, 7, 20, 3};
        P106ConstructBinaryTreefromInorderandPostorderTraversal solution
                = new P106ConstructBinaryTreefromInorderandPostorderTraversal();
        TreeNode root = solution.buildTree(inorder, postorder);
        System.out.println(root);
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = postorder.length - 1;
        return buildTree(inorder, postorder, 0, inorder.length - 1);
    }

    // Output: [3,9,20,null,null,15,7]
    public TreeNode buildTree(int[] inorder, int[] postorder, int start, int end) {

        if (end < 0 || start > inorder.length - 1 || start > end) {
            return null;
        }
        int value = postorder[index--];

        Integer integer = find(inorder, value, start, end);
        if (integer == -1) {
            return null;
        }
        TreeNode root = new TreeNode(value);
        root.right = buildTree(inorder, postorder, integer + 1, end);
        root.left = buildTree(inorder, postorder, start, integer - 1);

        return root;
    }

    public Integer find(int[] arr, int value, int start, int end) {
        for (int i = start; i <= end; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }

    //      Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
